package com.c2b.algorithm.newcoder;

/**
 * <a href='https://www.nowcoder.com/practice/b58434e200a648c589ca2063f1faf58c?tpId=295&tqId=23286&ru=%2Fexam%2Foj&qru=%2Fta%2Fformat-top101%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj'>链表内指定区间反转</a>
 *
 * @author c2b
 * @since 2024/3/14 9:46
 */
public class BM2ReverseBetween {

    public static class Solution {
        public ListNode reverseBetween(ListNode head, int m, int n) {
            if (head == null || m == n) {
                return head;
            }
            // 给链表添加一个虚拟的链表头
            ListNode dummyNode = new ListNode(-1);
            dummyNode.next = head;
            // 1.先找到m的前一个节点
            ListNode mPrevNode = dummyNode;
            for (int i = 1; i <= m - 1; i++) {
                mPrevNode = mPrevNode.next;
            }
            ListNode nNode = mPrevNode;
            // 2.再找到n位置的节点
            for (int i = m - 1; i < n; i++) {
                nNode = nNode.next;
            }
            //
            ListNode nNextNode = nNode.next;
            // 3.断开链表
            nNode.next = null;
            // 反转链表
            ListNode prev = null;
            ListNode currNode = mPrevNode.next;
            while (currNode != null) {
                ListNode next = currNode.next;
                currNode.next = prev;
                prev = currNode;
                currNode = next;
            }
            // 此时prev为反转后链表的头节点
            mPrevNode.next = prev;
            while (prev.next != null) {
                prev = prev.next;
            }
            prev.next = nNextNode;
            return dummyNode.next;
        }
    }

    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(1);
        listNode1.next = new ListNode(2);
        listNode1.next.next = new ListNode(3);
        listNode1.next.next.next = new ListNode(4);
        listNode1.next.next.next.next = new ListNode(5);

        Solution solution = new Solution();
        Printer.printListNode(solution.reverseBetween(listNode1, 2, 4));


        ListNode listNode2 = new ListNode(1);
        Printer.printListNode(solution.reverseBetween(listNode2, 1, 1));

        ListNode listNode3 = new ListNode(3);
        listNode3.next = new ListNode(5);
        Printer.printListNode(solution.reverseBetween(listNode3, 1, 2));
    }
}
